package com.xigua._树;

import com.xigua.TreeNode;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。
 * @date 2022/4/2810:54
 */
public class _111_二叉树的最小深度 {

    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        return dfs(root,1);
    }

    int dfs(TreeNode root,int height){
        if (root.right == null && root.left == null) return height;
        if (root.right == null) return dfs(root.left,height)+1;
        if (root.left == null) return dfs(root.right,height)+1;
        return Math.min(dfs(root.left,height)+1,dfs(root.right,height)+1);
    }

    public int minDepth1(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        if (root.right == null) return minDepth1(root.left)+1;
        if (root.left == null) return minDepth1(root.right)+1;
        return Math.min(minDepth1(root.left)+1,minDepth1(root.right)+1);
    }

}
